Context-adaptive arithmetic coding is a technique for entropy coding of bi-tonal images as evinced by a variety of current industry standards (e.g., Joint Bi-level Image Experts Group (JBIG, JBIG2), etc.). Essentially, pixels of an image are compressed into a series of bits that have a unique pattern. A compression algorithm maps a sequence of symbols embedded in the image being compressed into a real number interval. The compression algorithm successively divides the interval into sub-intervals based on inputted symbols parsed from the image and their associated probabilities (likelihoods that a parsed symbol is matched with a known symbol). The performance of the compression algorithm is in direct proportion to how well it does with estimating the symbol probabilities, because as symbols become known the compression algorithm adjusts itself if the estimations were incorrect.
A model is used by a compression algorithm to estimate symbol probabilities for input symbols based on contexts associated with the input symbols. The model maintains a state file for each context of each input symbol, and the model is updated as symbols are received and processed.
Decompression proceeds in a similar manner as compression. That is, compressed pixels represented as a series of bit values are acquired and their contexts are resolved. Based on contexts, a most likely symbol is determined and that most likely symbol is outputted as a portion of the decompressed image. Again, if the decompression algorithm does not estimate the symbols or pattern correctly, then the performance of decompression degrades as the decompression algorithm adjusts itself.
Because arithmetic decompression is heavily dependent on the contexts of previously processed compressed values and contexts of values that may have not yet been processed, the decompression performance becomes restricted. Thus, portions of the decoding remain idle until enough information becomes available to predict a context. Stated another way, sequential dependencies which are inherent in a binary compressed image restrict processing throughput of existing implementations of decompression algorithms to a tightly coupled process that linearly progresses.